package sword_offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName _57_2FindContinuousSequence
 * @Description: 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * 示例 2：
 *
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *  
 *
 * 限制：
 *
 * 1 <= target <= 10^5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/12 21:47
 */
public class _57_2FindContinuousSequence {

    public static void main(String[] args) {
        int[][] continuousSequence = new _57_2FindContinuousSequence().findContinuousSequence(9);
        System.out.println(Arrays.toString(continuousSequence));
    }

    public int[][] findContinuousSequence(int target) {
        if (target == 1){
            int[][] res = new int[1][1];
            res[0] = new int[]{1};
            return res;
        }
        List<List<Integer>> result = new LinkedList<>();
        int left = 1, right = 2, sum = left + right, maxIndex = (target >> 1) + 1;

        while (left < right && right <= maxIndex){
            if (sum < target){
                right++;
                sum += right;
            }else if (sum > target){
                sum -= left;
                left++;
            }else {
                // add to result
                saveToList(result, left, right);
                right++;
                sum += right;
            }
        }

        // 这里的转换颇为麻烦
        int[][] res = new int[result.size()][];// 知识点：创建二维数组时，第一维必须声明长度，二维可以不声明
        for (int i = 0; i < result.size(); i++) {
            int[] arr = new int[result.get(i).size()];
            for (int j = 0; j < result.get(i).size(); j++) {
                arr[j] = result.get(i).get(j);
            }
            res[i] = arr;
        }

        return res;
    }
    public void saveToList(List<List<Integer>> result, int left, int right){
        ArrayList<Integer> list = new ArrayList<>(right - left + 1);
        for (int i = left; i <= right; i++) {
            list.add(i);
        }
        result.add(list);
    }


}
